#include<iostream>
#include<list>
using namespace std;

//基数排序
template<typename T>
void RadixSort(T myarray[], int length)
{
	if (length <= 1) //不超过1个元素的数组，没必要排序
		return;
	
	T* pResult = new T[length]; //新数组，用于保存每趟排序的结果
	
	//借用C++标准库中的list容器保存必要的信息，当然也可以用自己写的链表来保存数据
	std::list<T *> mylist[10]; //#include <list>  ，注意list中的<>里的数据类型
	
	//3，意味着分别取得个位、十位、百位 数字
	for (int i = 0; i < 3; ++i) //为简化代码，假设已经知道待排序数字最大不超过3位，所以这里就直接写i < 3了
	{
		//(1)分配
		for (int j = 0; j < length; ++j)
		{
			//根据i值来决定取得某个数字的个位、十位、百位
			int tmpi = i;
			T tmpvalue = myarray[j];
			T lastvalue;   //取得的个位、十位、百位数字保存在这里
			while (tmpi >= 0)
			{
				lastvalue = tmpvalue % 10;
				tmpvalue /= 10;
				tmpi--;
			} //end while
			
			mylist[lastvalue].push_back(&myarray[j]);  //在list尾部插入元素
		} //end for j
		
		//(2)收集
		int idx = 0;
		for (int k = 0; k < 10; ++k)
		{
			for (auto iter = mylist[k].begin(); iter != mylist[k].end(); ++iter)
			{
				pResult[idx] = *( * (iter));
				idx++;
			} //end iter
			mylist[k].clear(); //清空mylist,为下次向其中存数据做准备
		} //end for k
		
		//(3)把数据拷贝回myarray
		for (int m = 0; m < length; ++m)
		{
			myarray[m] = pResult[m];
		}//end for m
	} //end for i
	
	delete[] pResult;
	return;
}



int main()
{
	int arr[] = { 516, 231, 445, 323, 299, 2, 18, 67, 42, 102, 164, 755, 687, 437 };
	int length = sizeof(arr) / sizeof(arr[0]);   //数组中元素个数
	RadixSort(arr, length);//对数组元素进行基数排序
	cout <<"基数排序结果为：";
	for (int i = 0; i < length; ++i)
	{
		cout << arr[i] <<"";
	}
	cout << endl; //换行
	
	return 0;
}
